package com.atguigui.leetcode;

/**
 * 556.下一个更大元素 III
 * Project: leetcode
 * Package: com.atguigui.leetcode
 * Version: 1.0
 * <p>
 * Created by  wangjiaxin  on 2022/7/3 18:17
 */
public class P556NextGreaterElementIii {
    public static void main(String[] args) {
        Solution solution = new P556NextGreaterElementIii().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int nextGreaterElement(int n) {

            char[] chars = Integer.toString(n).toCharArray();

            int i = chars.length - 2;
            while (i >= 0 && chars[i] >= chars[i + 1]) {
                i--;
            }
            if (i < 0) {
                return -1;
            }

            int j = chars.length - 1;
            while (j >= 0 && chars[i] >= chars[j]) {
                j--;
            }
            //互换这两个数
            swap(chars, i, j);

            reverse(chars, i + 1);

            // 这里要转换一下，注意边界问题
            long ans = Long.parseLong(new String(chars));
            // 如果大于了32位整数就返回-1
            return ans > Integer.MAX_VALUE ? -1 : (int) ans;
        }

        private void reverse(char[] chars, int start) {
            int left = start, right = chars.length - 1;
            while (left < right) {
                swap(chars, left, right);
                left++;
                right--;
            }
        }

        private void swap(char[] chars, int i, int j) {
            char num = chars[i];
            chars[i] = chars[j];
            chars[j] = num;
        }
    }
}
